package com.demo.java.OD601_650.OD650;

import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最长回文字符串(A卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/147039082
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 输入字符串
        String input_str = in.nextLine();

        // 哈希表，用于统计每个字符的出现次数
        HashMap<Character, Integer> char_count = new HashMap<>();

        // 统计字符出现次数
        for (int i = 0; i < input_str.length(); i++) {
            char c = input_str.charAt(i);
            if (char_count.containsKey(c)) {
                // 如果字符已出现，次数+1
                char_count.put(c, char_count.get(c) + 1);
            } else {
                // 如果字符没有出现过，初始化次数为1
                char_count.put(c, 1);
            }
        }

        // 用于存储偶数次的字符和奇数次的字符
        ArrayList<Character> even_chars = new ArrayList<>();
        ArrayList<Character> odd_chars = new ArrayList<>();

        // 遍历哈希表，分离偶数次和奇数次的字符
        for (char c : char_count.keySet()) {
            int count = char_count.get(c);
            if (count >= 2) {
                // 如果出现次数大于等于2，则可以成对放置到回文两侧
                for (int i = 0; i < count / 2; i++) {
                    even_chars.add(c);
                }
            }

            // 如果出现次数是奇数，添加到奇数列表中
            if (count % 2 != 0) {
                odd_chars.add(c);
            }
        }

        // 对偶数次字符进行排序
        even_chars.sort((a, b) -> a - b);
        // 左侧部分：按字典序排序后的字符
        String left_str = even_chars.stream().map(Object::toString)
                .collect(Collectors.joining(""));

        // 中间部分：如果有奇数次的字符，取最小的一个作为回文中心
        String mid_str = "";
        if (odd_chars.size() > 0) {
            odd_chars.sort((a, b) -> a - b);
            mid_str = odd_chars.get(0) + "";
        }

        // 右侧部分：偶数次字符的反向排序
        even_chars.sort((a, b) -> b - a);
        String right_str = even_chars.stream().map(Object::toString)
                .collect(Collectors.joining(""));

        // 输出最终的回文字符串
        System.out.println(left_str + mid_str + right_str);
    }
}